Termination by completion
Identifieur interne : 00DE15 ( Main/Exploration ); précédent : 00DE14; suivant : 00DE16Termination by completion
Auteurs : Françoise Bellegarde [États-Unis] ; Pierre Lescanne [France]Source :
- Applicable Algebra in Engineering, Communication and Computing [ 0938-1279 ] ; 1990-09-01.
English descriptors
- KwdEn :
- Teeft :
- Assoc, Assoc endo, Bachmair, Bellegarde, Completion procedure, Completion procedures, Comput, Computer science, Confluent, Critical pair, Critical pairs, Data structure, Dershowitz, Endomorphism, Lecture notes, Lescanne, Lexicographic, Lexicographic path, Local confluence, Local cooperation, Natural numbers, Noetherian, Normal form, Operator symbols, Recursive, Recursive decomposition, Recursive path, Replacement property, Right lexicographic status, Rule assoc, Simplification orderings, Technical report, Termination, Transition rules, Transitive closure.
Abstract
Abstract: This paper presents a completion procedure for proving termination of term rewrite systems. It works as follows. Given a term rewrite systemR supposed to terminate and a term rewrite systemT used to transformR, the completion builds an auxiliary term rewrite systemS, the system transformed ofR byT. The termination ofS andT associated with a property called local cooperation implies the termination ofR. If the process terminates this provides a mechanical proof of the termination ofR.
Url:
DOI: 10.1007/BF01810293
Affiliations:
- France, États-Unis
- Grand Est, Lorraine (région), Washington (État)
- Nancy, Vandœuvre-lès-Nancy
- Centre national de la recherche scientifique, Institut national de recherche en informatique et en automatique, Laboratoire lorrain de recherche en informatique et ses applications, Université de Lorraine
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000899
- to stream Istex, to step Curation: 000894
- to stream Istex, to step Checkpoint: 003221
- to stream Main, to step Merge: 00E695
- to stream Main, to step Curation: 00DE15
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Termination by completion</title><author><name sortKey="Bellegarde, Francoise" sort="Bellegarde, Francoise" uniqKey="Bellegarde F" first="Françoise" last="Bellegarde">Françoise Bellegarde</name></author><author><name sortKey="Lescanne, Pierre" sort="Lescanne, Pierre" uniqKey="Lescanne P" first="Pierre" last="Lescanne">Pierre Lescanne</name><affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="region" nuts="2">Lorraine (région)</region></placeName><orgName type="laboratoire" n="5">Laboratoire lorrain de recherche en informatique et ses applications</orgName><orgName type="university">Université de Lorraine</orgName><orgName type="institution">Centre national de la recherche scientifique</orgName><orgName type="institution">Institut national de recherche en informatique et en automatique</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:275375A9F7EEA0915D41F0FCC1F0E92A9008168C</idno><date when="1990" year="1990">1990</date><idno type="doi">10.1007/BF01810293</idno><idno type="url">https://api.istex.fr/ark:/67375/1BB-G4WFB6XR-Z/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000899</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000899</idno><idno type="wicri:Area/Istex/Curation">000894</idno><idno type="wicri:Area/Istex/Checkpoint">003221</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">003221</idno><idno type="wicri:doubleKey">0938-1279:1990:Bellegarde F:termination:by:completion</idno><idno type="wicri:Area/Main/Merge">00E695</idno><idno type="wicri:Area/Main/Curation">00DE15</idno><idno type="wicri:Area/Main/Exploration">00DE15</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Termination by completion</title><author><name sortKey="Bellegarde, Francoise" sort="Bellegarde, Francoise" uniqKey="Bellegarde F" first="Françoise" last="Bellegarde">Françoise Bellegarde</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Western Washington University, 98225, Bellingham, WA</wicri:regionArea><placeName><region type="state">Washington (État)</region></placeName></affiliation></author><author><name sortKey="Lescanne, Pierre" sort="Lescanne, Pierre" uniqKey="Lescanne P" first="Pierre" last="Lescanne">Pierre Lescanne</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Centre de Recherche en Informatique de Nancy, CNRS and INRIA-Lorraine, Domaine Scientifique Victor Grignard, BP 239, F-54506, Vandœuvre-lès-Nancy</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Vandœuvre-lès-Nancy</settlement></placeName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="region" nuts="2">Lorraine (région)</region></placeName><orgName type="laboratoire" n="5">Laboratoire lorrain de recherche en informatique et ses applications</orgName><orgName type="university">Université de Lorraine</orgName><orgName type="institution">Centre national de la recherche scientifique</orgName><orgName type="institution">Institut national de recherche en informatique et en automatique</orgName></affiliation></author></analytic><monogr></monogr><series><title level="j">Applicable Algebra in Engineering, Communication and Computing</title><title level="j" type="abbrev">AAECC</title><idno type="ISSN">0938-1279</idno><idno type="eISSN">1432-0622</idno><imprint><publisher>Springer-Verlag</publisher><pubPlace>Berlin/Heidelberg</pubPlace><date type="published" when="1990-09-01">1990-09-01</date><biblScope unit="volume">1</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="79">79</biblScope><biblScope unit="page" to="96">96</biblScope></imprint><idno type="ISSN">0938-1279</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0938-1279</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Completion</term><term>Term rewriting</term><term>Termination</term><term>Well-foundedness</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Assoc</term><term>Assoc endo</term><term>Bachmair</term><term>Bellegarde</term><term>Completion procedure</term><term>Completion procedures</term><term>Comput</term><term>Computer science</term><term>Confluent</term><term>Critical pair</term><term>Critical pairs</term><term>Data structure</term><term>Dershowitz</term><term>Endomorphism</term><term>Lecture notes</term><term>Lescanne</term><term>Lexicographic</term><term>Lexicographic path</term><term>Local confluence</term><term>Local cooperation</term><term>Natural numbers</term><term>Noetherian</term><term>Normal form</term><term>Operator symbols</term><term>Recursive</term><term>Recursive decomposition</term><term>Recursive path</term><term>Replacement property</term><term>Right lexicographic status</term><term>Rule assoc</term><term>Simplification orderings</term><term>Technical report</term><term>Termination</term><term>Transition rules</term><term>Transitive closure</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: This paper presents a completion procedure for proving termination of term rewrite systems. It works as follows. Given a term rewrite systemR supposed to terminate and a term rewrite systemT used to transformR, the completion builds an auxiliary term rewrite systemS, the system transformed ofR byT. The termination ofS andT associated with a property called local cooperation implies the termination ofR. If the process terminates this provides a mechanical proof of the termination ofR.</div></front></TEI><affiliations><list><country><li>France</li><li>États-Unis</li></country><region><li>Grand Est</li><li>Lorraine (région)</li><li>Washington (État)</li></region><settlement><li>Nancy</li><li>Vandœuvre-lès-Nancy</li></settlement><orgName><li>Centre national de la recherche scientifique</li><li>Institut national de recherche en informatique et en automatique</li><li>Laboratoire lorrain de recherche en informatique et ses applications</li><li>Université de Lorraine</li></orgName></list><tree><country name="États-Unis"><region name="Washington (État)"><name sortKey="Bellegarde, Francoise" sort="Bellegarde, Francoise" uniqKey="Bellegarde F" first="Françoise" last="Bellegarde">Françoise Bellegarde</name></region></country><country name="France"><region name="Grand Est"><name sortKey="Lescanne, Pierre" sort="Lescanne, Pierre" uniqKey="Lescanne P" first="Pierre" last="Lescanne">Pierre Lescanne</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00DE15 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00DE15 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:275375A9F7EEA0915D41F0FCC1F0E92A9008168C
|texte= Termination by completion
}}
| This area was generated with Dilib version V0.6.33. |  |